package algorithm_demo.demo_advanced;

import java.util.LinkedList;

/**
 * 给定一个整型数组arr，和一个整数num
 * 某个arr中的子数组sub，如果想达标，必须满足：
 * sub中最大值-sub中最小值<=num，
 * 返回arr中达标子数组的数量
 *
 * @author Api
 * @date 2023/3/24 6:27
 */
public class Code02_AllLessNumSubArray {
    /*暴力*/
    public static int getNumBao(int[] arr, int num){
        if (arr == null || arr.length == 0){
            return 0;
        }
        int valid = 0;
        for(int L = 0;L<arr.length;L++){
            for(int R = L; R<arr.length;R++){
                int max = arr[L];
                int min = arr[R];
                for(int i = L+1;i<=R;i++){
                    max = Math.max(max, arr[i]);
                    min = Math.min(min, arr[i]);
                }
                if (max-min<=num){
                    valid++;
                }
            }
        }
        return valid;
    }
    /*
    * 如果arr[L..R]中满足max-min<=num，那么arr[L'..R']中也满足L<L',R'<R
    * 结论1：如果[L...R] 范围上的max - min <= sum，那么 L...R 范围的所有子数组都是达标的
    * 原因：假设 L'...R'是L...R的子数组，因为[L...R]max - [L...R]min <= sum，那么[L'...R']的max'<= max，而[L'...R']的min' >= min，
    *      所以max'- min' <= sum，也是达标的
    * 结论2：如果[L...R] 范围上的max - min > sum，那么无论L往左扩还是R往右扩，产生的新的子数组一定是不达标的
    *
    * 思路：个准备一个最大值和最小值的更新结构qmax和qmin，用于维护最大值和最小值
    * 假设窗口一开始为0，此时L = 0，让R往右扩，每扩一次就更新qmax和qmin，如果达标就继续扩，一直到p位置不达标了，那么必须以0开始的子数组达标的数量一共有p-0+1 = p+1个；
    * 然后L往右滑动到1，即L=1的时候，R继续往右扩，看是否达标，直到到达不能达标的位置，则能得到必须以1开始的子数组的达标数量；
    * index: 0,1,2,3,4,5,6,...,N-1
    * 如果满足：0-4是达标的，到5则不达标时，那么0-4内的子数组均达标即以0开头的子数组为：0-1,0-2,0-3,0-4，从5开始到最后N-1均不达标
    * 下一次则为1-（N-1）开始
    */

    public static int getNum(int[] arr, int num){
        if (arr == null || arr.length == 0){
            return 0;
        }
        LinkedList<Integer> qmin = new LinkedList<Integer>();
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        int L = 0;
        int R = 0;
        //[L..R)->[0,0)窗口内无数 [1,1)无数
        int res = 0;
        while(L<arr.length){ //L是开头位置，尝试每一个开头
            //如果此时窗口的开头是L，下面的while工作：R向右扩到违规为止
            while(R<arr.length){//R是最后一个达标位置的再下一个
                while(!qmin.isEmpty() && arr[qmin.peekLast()]>=arr[R]){
                    qmin.pollLast();
                }
                qmin.addLast(R);
                //R->arr[R]
                while(!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]){
                    qmax.pollLast();
                }
                qmax.addLast(R);
                if (null != qmin.peekFirst() && null != qmax.peekFirst()
                    && arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num){
                    break;
                }
                R++;
            }
            //R是最后一个达标位置的再下一个，第一个违规的位置
            res += R-L;
            if (null != qmin.peekFirst() && qmin.peekFirst() == L){
                qmin.pollFirst();
            }
            if (null != qmax.peekFirst() && qmax.peekFirst() == L){
                qmax.pollFirst();
            }
            L++;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {4,3,2,12,34,45,23,12};
        getNum(arr, 10);
    }
}
